package _12_左程云;

public class Code01_Sort {

    // 选择排序，时间复杂度 O(n^2)
    public void selectionSort(int[] nums) {
        if (nums==null || nums.length < 2) return;

        // 每次从 i~N 位置选择最小值，并交换到 i 位置，每次确定第i个位置的值
        for (int i = 0; i < nums.length-1; i++) {
            int minIndex = i;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            swap(nums, i, minIndex);
        }
    }

    // 冒泡排序，时间复杂度 O(n^2)
    public void bubbleSort(int[] nums) {
        if (nums==null || nums.length < 2) return;
        for (int r = nums.length-1; r > 0; r--) {
            for (int i = 0; i < r; i++) {
                if (nums[i] > nums[i+1]) {
                    swap(nums, i, i+1);
                }
            }
        }
    }

    // 插入排序，时间复杂度 O(n^2)，不稳定，最差是平方复杂度
    public void insertionSort(int[] nums) {
        if (nums==null || nums.length < 2) return;
        // 模拟打牌，每次让 0~i 有序
        for (int i = 1; i < nums.length; i++) {
            // 对位置 i 的数，与之前的所有相邻数比较，如果 小于 则交换
            for (int j = i-1; j>=0 && nums[j]>nums[j+1]; j--) {
                swap(nums, j, j+1);
            }
        }
    }

    /**
     * int a = 10       a = x;
     * int b = 20       b = y;
     * a = a ^ b;       a = x^y;  b = y;
     * b = a ^ b;       a = x^y;  b = x^y^y = x;
     * a = a ^ b;       a = x^y^x = y;  b = x;
     */
    public void swap(int[] nums, int i, int j) {
        if (i == j) return;
        nums[i] = nums[i] ^ nums[j];
        nums[j] = nums[i] ^ nums[j];
        nums[i] = nums[i] ^ nums[j];
    }

}
